package leetcode;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-17 14:15
 **/
public class LeetCode1220 {

    //滚动数组优化
    public int countVowelPermutation(int n) {
        int mod = 1000000007;
        long p1 = 1;
        long p2 = 1;
        long p3 = 1;
        long p4 = 1;
        long p5 = 1;
        for (int i = 2; i <= n; ++i) {
            long t1 = p1;
            long t2 = p2;
            long t3 = p3;
            long t4 = p4;
            long t5 = p5;

            p1 = (t2 + t3 + t5) % mod;
            p2 = (t1 + t3) % mod;
            p3 = (t2 + t4) % mod;
            p4 = t3 % mod;
            p5 = (t3 + t4) % mod;
        }

        long sum = 0;
        sum = (sum + p1) % mod;
        sum = (sum + p2) % mod;
        sum = (sum + p3) % mod;
        sum = (sum + p4) % mod;
        sum = (sum + p5) % mod;
        return (int) sum;
    }

    //动态规划
    /*public int countVowelPermutation(int n) {
        //dp[i][j]: 表示在长度为i时,以j结尾的字符串个数,i的映射关系为{0:a,1:e,2:i,3:o,4:u}
        long[][] dp = new long[n + 1][5];
        int mod = 1000000007;
        Arrays.fill(dp[1], 1);
        for (int i = 2; i <= n; ++i) {
            dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % mod;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
            dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % mod;
            dp[i][3] = (dp[i - 1][2]) % mod;
            dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % mod;
        }

        long sum = 0;
        for (int i = 0; i < 5; i++) {
            sum = (sum + dp[n][i]) % mod;
        }
        return (int) sum;
    }*/

}
